
def n_choose_k(vals, size)
  @goods = []
  @sums = []
  puts "average sum of #{vals} choose #{size}"
  a = n_choose_k_helper(0, 0, size, vals, [])
  sum1 = @sums.inject(0){|memo, i| memo + i}
  puts "#{sum1/@sums.size}"
  puts "average sum of #{vals} choose #{size}"
  sum2 = fast_sum vals, size
  puts "#{sum2}"
end


def fast_sum(vals, size)
  lt = generate_n_choose_k
  num_sets_in = lt[vals.size - 1][size - 1]
  num_sets = lt[vals.size][size]
  
  t_sum = vals.inject(0){|memo, v| memo + (v * num_sets_in)}
  t_sum / num_sets
end

def n_choose_k_helper(start, num, target, vals, current)
  e = vals.size - target + num
  if num == target
    @goods << current
    @sums << current.inject(0){|memo, i| memo + i}
    return current
  end
  rets = []
  (start..e).each do |i|
    new_a = current + [vals[i]]
    #puts "new_a is #{new_a}"
    res = n_choose_k_helper(i+1, num+1, target, vals, new_a)
    rets <<  res
  end
  rets
end

def generate_n_choose_k
  lookup_table = []
  #initialize
  (0..28).each {|n| lookup_table[n] = [1]}
  (1..28).each {|k| lookup_table[0][k] = 0}
  
  (1..28).each do |n|
    
    (1..28).each do |k|
      
      lookup_table[n][k] = lookup_table[n-1][k-1] + lookup_table[n-1][k]
    
    end
    
  end
  
  lookup_table
  
end

def go(a = nil, num = 1)
  arr = a || [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19, 20]
  pulls = []
  (1..300).each do 
    n = test_prob(arr.dup, num)
    pulls << n
  end
  average_pulls = pulls.inject(0){|memo, v| memo + v}.to_f / pulls.size.to_f
  puts "::DONE:: average pull is #{average_pulls}"
end

def test_prob(a, num_targs)
  r = Random.new
  targets = []
  
  cont = true
  while(targets.size < num_targs)
    i = rand(a.size)
    targets << a[i] unless targets.include? a[i]
  end
  
  found = false
  pulls = 0
  while(found == false)
    i = r.rand(a.size)
    if targets.include? a[i]
      found = true
    else
      a.delete_at(i)
    end
    pulls = pulls + 1
  end
  
  puts "found it took #{pulls} pulls size of a is #{a.size} looking for #{targets}"
  pulls
  
end













